package Aleehot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * ClassName: c061_2
 * Package: Aleehot100
 * Description: 131. 分割回文串
 *
 * @Author BCXJ
 * @Create 2025/8/12 20:48
 * @Version 1.0
 * @Since 1.0
 */
public class c061_2 {

    public static void main(String[] args) {
        partition("cbbbcc");

        for (boolean[] booleans : flag) {
            System.out.println(Arrays.toString(booleans));
        }
        System.out.println(res);
    }

    static boolean[][] flag = new boolean[16][16];
    static List<List<String>> res = new ArrayList<>();
    static int len;
    public static List<List<String>> partition(String s) {
        // 动态规划 - 找出 s中全部的回文串的位置, 
        for (boolean[] booleans : flag) {
            Arrays.fill(booleans,  false);
        }
        char[] arr = s.toCharArray();
        len = s.length();
        res.clear();
        // 看一下ai的做法，非常的奇妙
        for (int i = 0; i < len; i++) {
            flag[i][i] = true;
            if(i != len - 1) { // 不是最后一行
                flag[i][i + 1] = arr[i] == arr[i + 1];
            }
        }
        // 动态规划 - 可以画一下图，看看这个dp的生成规律
        for (int i = 0, j = i + 2; j < len; j ++) {
            for (int l = i, r = j; r < len; l++,  r++) {
                flag[l][r] = arr[l] == arr[r] && flag[l + 1][r - 1];
            }
        }
        backtrack(s, 0, new ArrayList<>());
        return res;
    }
    private static void backtrack(String s, int start, List<String> path) {
        if(start == len) {
            res.add(new ArrayList<>(path));
        }

        // 从start 开始分割
        for (int i = start; i < len; i++) {
            if(flag[start][i]) {
                String substring = s.substring(start, i + 1);
                path.add(substring);
                backtrack(s, i + 1, path);
                path.remove(path.size() - 1);
            }
        }
    }


    // 下面的是 GPT5的实现，可以说是做到了极致的简洁
    /*
    public List<List<String>> partition(String s) {
        int n = s.length();
        List<List<String>> res = new ArrayList<>();
        List<String> path = new ArrayList<>();

        // 1. 预处理回文表
        boolean[][] dp = new boolean[n][n];
        for (int right = 0; right < n; right++) {
            for (int left = 0; left <= right; left++) {
                if (s.charAt(left) == s.charAt(right) &&
                    (right - left <= 2 || dp[left + 1][right - 1])) {
                    dp[left][right] = true;
                }
            }
        }

        // 2. 回溯切分
        backtrack(s, 0, path, res, dp);
        return res;
    }

    private void backtrack(String s, int start, List<String> path, List<List<String>> res, boolean[][] dp) {
        if (start == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (dp[start][i]) { // O(1) 查询
                path.add(s.substring(start, i + 1));
                backtrack(s, i + 1, path, res, dp);
                path.remove(path.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        PalindromePartitioning solver = new PalindromePartitioning();
        System.out.println(solver.partition("aab"));
        // 输出: [[a, a, b], [aa, b]]
    }
     */
}
